package com.lmk.dsa.algorithm.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import com.lmk.dsa.struct.commons.BstNode;
import com.lmk.dsa.struct.tree.BST;

/**
 * 二叉树遍历
 * @author LaoMake
 * @since 1.0
 */
public class BstTraverse<K extends Comparable<? super K>, V> {

    /** 树的引用 */
    private BST<K, V> tree;

    /** 树的根节点 */
    private BstNode<K, V> root;

    /** 树的节点个数 */
    private int size;

    public BstTraverse(BST<K, V> tree) {
        this.tree = tree;
        this.root = tree.root();
        this.size = tree.size();
    }

    /**
     * 广度优先遍历
     * @return
     */
    public List<BstNode<K, V>> bfs() {
        List<BstNode<K, V>> nodeList = new ArrayList(size);
        Queue<BstNode<K, V>> queue = new LinkedList();
        queue.offer(root);

        BstNode<K, V> node;
        while (!queue.isEmpty()){
            node = queue.poll();
            nodeList.add(node);
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }

        return nodeList;
    }

    /**
     * DFS: 前序遍历
     * @return
     */
    public List<BstNode<K, V>> dlr() {
        List<BstNode<K, V>> itemList = new ArrayList<>(size);
        dlr(root, itemList);
        return itemList;
    }

    /**
     * 前序遍历，填充数据列表
     * @param node
     * @param itemList
     */
    private void dlr(BstNode<K, V> node, List<BstNode<K, V>> itemList) {
        if(node == null){
            return;
        }
        itemList.add(node);
        dlr(node.left, itemList);
        dlr(node.right, itemList);
    }

    /**
     * DFS: 中序遍历
     * @return
     */
    public List<BstNode<K, V>> ldr() {
        List<BstNode<K, V>> itemList = new ArrayList<>(size);
        ldr(root, itemList);
        return itemList;
    }

    /**
     * 中序遍历，填充数据列表
     * @param node
     * @param itemList
     */
    private void ldr(BstNode<K, V> node, List<BstNode<K, V>> itemList) {
        if(node == null){
            return;
        }

        ldr(node.left, itemList);
        itemList.add(node);
        ldr(node.right, itemList);
    }

    /**
     * DFS: 后序遍历
     * @return
     */
    public List<BstNode<K, V>> lrd() {
        List<BstNode<K, V>> itemList = new ArrayList<>(size);
        lrd(root, itemList);
        return itemList;
    }

    /**
     * 后序遍历，填充数据列表
     * @param node
     * @param itemList
     */
    private void lrd(BstNode<K, V> node, List<BstNode<K, V>> itemList) {
        if(node == null){
            return;
        }
        ldr(node.left, itemList);
        ldr(node.right, itemList);
        itemList.add(node);
    }

    /**
     * 判断该树是否为二分搜索树
     * @return
     */
    public boolean isBST() {
        boolean ok = true;
        List<BstNode<K, V>> nodes = ldr();
        K key = null;
        for (BstNode<K, V> n : nodes){
            if(key == null){
                key = n.key;
                continue;
            }else{
                if(n.key.compareTo(key) < 0){
                    ok = false;
                    break;
                }
            }
        }
        return ok;
    }
}
